#include <vector>
#include <iostream>

using namespace std;

/* 插入排序 InsertionSort
 *  0  1     ...   5      
 * [8, 5, 2, 9, 6, 3]
                   ^右手
 * [2, 3, 5, 6, 8, 9] 左手
*/
// 递归的实现方式
// 函数调用它自己
// 左手             右手
// []              8 <- 用插入排序把 8 插入到数组 [] 里
// [8]             5 <- 用插入排序把 5 插入到数组 [8] 里
// [5, 8]          2 <- 用插入排序把 2 插入到数组 [5, 8] 里
// [2, 5, 8]       9 <- 用插入排序把 9 插入到数组 [2, 5, 8] 里
// [2, 5, 8, 9]    6 <- 用插入排序把 6 插入到数组 [2, 5, 8, 9] 里
// [2, 5, 6, 8, 9] 3 <- 用插入排序把 3 插入到数组 [2, 5, 6, 8, 9] 里
//
// 都是把右手的牌，插入到左手已经排序好的数组里
// 最后一个插入位置是 5
// 当插入位置是 6 的时候，排序就结束了
// Recursive 递归
// insertSortRecursive(v, 1)
//   insertSortRecursive(v, 2)
//     insertSortRecursive(v, 3)
//       insertSortRecursive(v, 4)
//         insertSortRecursive(v, 5)
//           insertSortRecursive(v, 6)
vector<int> insertionSortRecursive(vector<int> array, int nextPos) {
  if (nextPos == array.size()) {
    return array;
  }

  int i = nextPos;
  while (i > 0 && array[i - 1] > array[i]) {
    swap(array[i - 1], array[i]);
    --i;
  }

  return insertionSortRecursive(array, nextPos + 1);
}
// 右手没牌了
// 左手的牌 [2, 3, 5, 6, 8, 9]


// 插入排序的过程式实现
vector<int> insertionSort(vector<int> array) {
  for (int i = 1; i < array.size(); ++i) {
    // i 表示的就是右手的位置
    // 对于每一个位置 i

    int j = i; // j 表示的是左手的位置

    while (j > 0 && array[j - 1] > array[j]) {
      swap(array[j - 1], array[j]);
      --j;
    }
  }

  return array;
}

int main(int argc, char const *argv[])
{
  /* code */
  vector<int> v {
    8, 5, 2, 9, 6, 3
  }

  for (int n : insertionSortRecursive(v, 1)) {
    cout<<n<<" ";
  }
  cout<<end;

  return 0;
}
